| 翻訳と辞書 |
| Brooks’ theorem ： ウィキペディア英語版 |
Brooks' theorem
In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.
The theorem is named after R. Leonard Brooks, who published a proof of it in 1941. A coloring with the number of colors described by Brooks' theorem is sometimes called a ''Brooks coloring'' or a Δ-''coloring''.
==Formal statement==
For any connected undirected graph ''G'' with maximum degree Δ,
the chromatic number of ''G'' is at most Δ unless ''G'' is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Brooks' theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|